#include <stack>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<ListNode*> stack1, stack2;
        while (l1 != nullptr) {
            stack1.push(l1);
            l1 = l1->next;
        }
        while (l2 != nullptr) {
            stack2.push(l2);
            l2 = l2->next;
        }
        int step = 0;
        ListNode* pre = nullptr;
        while (!stack1.empty() || !stack2.empty() || step) {
            int val = step;
            if (!stack1.empty()) {
                val += stack1.top()->val;
                stack1.pop();
            }
            if (!stack2.empty()) {
                val += stack2.top()->val;
                stack2.pop();
            }
            step = val / 10;
            ListNode* l = new ListNode(val % 10);
            l -> next = pre;
            pre = l;
        }
        return pre;
    }
};
